package main

import (
	"fmt"
	"go-study/algorithm/standard"
	"math"
)

// 如何在二叉树中找出路径最大的和

func main() {
	data := []int{-2, 3, 5}
	root := standard.ArrayToTree(data, 0, len(data)-1)
	fmt.Println(findMaxPath(root))
}

var maxValue = math.MinInt64

func getMax(a, b, c int) int {
	var max int
	if a > b {
		max = a
	} else {
		max = c
	}
	if max < c {
		max = c
	}
	return max
}

func findMaxPathRecursive(root *standard.BNode) int {
	if root == nil {
		return 0
	}

	// 求左子树以 root.Left 为起始点的最大路径和
	sumLeft := findMaxPathRecursive(root.LeftChild)
	// 求右子树以 root.Right 为起始点的最大路径和
	sumRight := findMaxPathRecursive(root.RightChild)

	// 求以 root 为起点节点，叶子节点为结束节点的最大路径和
	allMax := root.Data.(int) + sumLeft + sumRight
	leftMax := root.Data.(int) + sumLeft
	rightMax := root.Data.(int) + sumRight

	tmp := getMax(allMax, leftMax, rightMax)

	if tmp > maxValue {
		maxValue = tmp
	}

	var subMax int
	if sumLeft > sumRight {
		subMax = sumLeft
	} else {
		subMax = sumRight
	}

	if subMax < 0 {
		subMax = 0
	}

	return root.Data.(int) + subMax
}

func findMaxPath(root *standard.BNode) int {
	findMaxPathRecursive(root)
	return maxValue
}
